This invention relates to coding and decoding of digital data, and more particularly to methods and apparatus for rapidly decoding streams of encoded, packed, unaligned, variable-length code words.
Medical image data, when digitally encoded, usually contains a large amount of redundancy because the digital representation allows each pixel to assume any value independent of the value of neighboring pixels. However, in real images, the value of each pixel rarely differs from that of its neighbors by more than a small amount. Various other types of data acquired or sampled from real-world signals have similar characteristics. As a result, uncompressed data of this type requires unnecessarily large amounts of storage space, and requires an unacceptably long time to transfer via input/output devices, communications channels, and the like.
In order to reduce the volume of this data, the approaches which are customarily used in the art employ such techniques as delta pulse code modulation (DPCM) and run length encoding to reduce the spatial correlation of the data, and employ variable word length (VWL) coding to compactly represent the decorrelated data. In these techniques, the fixed-length data are converted to variable-length codewords according to the statistics of the data. In general, the lengths of the codewords are chosen so that the most frequently occurring data are represented by shorter codewords, and infrequently occurring data are represented by longer codewords. As a result of properly assigning the variable-length codewords to the entire set of source symbols, the average codeword size of the VWL-encoded data is less than that of the original data, and thus compression is achieved.
Generally, the encoding process can be implemented by a table-lookup process using the decorrelated input data to address the table. Each entry of the table contains the output codeword and a data field specifying the codeword's length. The code length then controls subsequent hardware, such as an output shift register for a communications channel, or combinatorial bit-packing logic for output to fixed-word-length devices such as a computer or digital data storage system. A combinatorial method of this type employing a barrel shifter is described in Arbeiter U.S. Pat. No. 5,060,242.
Recovery of the original data, however, is slowed down by the decoding process, which is more complicated than the original coding process. Each VWL codeword must be extracted from the received bit stream before it is decoded into a source symbol Until the codeword is decoded, the starting bit position of the next codeword is not known. This limits the designer's ability to use multistage pipelined hardware to enhance throughput.
There are several methods of decoding VWL codewords. A traditional approach is to use a tree-searching algorithm. A VWL code can always be represented by a tree with codewords as leaves. The decoding process starts at the root of the treed and is guided to follow one of two branches at each node, according to the next bit from the input data stream. When a leaf is reached, the end of the codeword is detected. The most common hardware design for a tree-search decoder consists of a memory containing the decoding table, with a pair of entries for each node. The data bit being decoded is connected to the low order bit of the table address, and thus determines which branch of the tree will be selected at each node, i.e. which of the pair of entries will be selected in the current decoding step. Each of these entries has a one-bit data field identifying it as either a leaf or as a pointer to another node, and another data field containing either the decoded value (if a leaf) or (if not a leaf) the table address of the next pair of node entries. This hardware implementation requires a table lookup for each bit of the input bit stream, and is thus limited in its speed.
A table-lookup based approach is an alternative to the bit-by-bit tree search method. A table lookup approach is disclosed in Raviv et al. U.S. Pat. No. 3,675,212. In Raviv's approach, the received bit string is compared with the contents of a codeword table stored in an associative memory device. The Code table has an entry associated with each possible VWL codeword. Each entry includes the decoded fixed-length input word and the length of the variable length codeword. When the sequence of leading bits in an input register matches one of the entries of the codeword table, a codeword match is indicated. The input register is then shifted by the number of bits indicated by the code length entry, thereby making the next sequence of bits available for comparison with entries in the codeword table. Feedback to the input is required to inform the input register of the number of bits to shift after each variable length word is decoded.
A somewhat faster table-lookup decoding approach than Raviv's in described in Arbeiter U.S. Pat. No. 5,060,242. A combinatorial barrel shifter, rather than a shift register, is used to shift the input data into proper bit alignment for the decoding table.
In all of the above approaches, the feedback of the word length defeats attempts at pipelining the decoding process, and thus limits the speed of the decoder.
An alternative approach, which employs a feedforward technique, is described in Cordell U.S. Pat. No. 5,055,841. There the input bit stream enters a shift register at a fixed bit rate, and the parallel output of the shift register is connected to a programmable logic array (PLA) which functions as an associative memory device. The PLA is capable of decoding and translating the VWL code in each cycle of the shift register clock. The decoded output word is only transferred into the output latches, however, in the shift cycle when the VWL code is correctly aligned at the input to the PLA, as determined by a counter loaded with the length of the most recent VWL code. Due to the high speed of the PLA and the ability use delay-matching techniques in the feedforward signal paths, this method is fast. However, it still relies on decoding and decision-making on the time scale of the serial bit rate, and requires extremely fast components to keep up with the 155 Mhz bit rate specified for the high definition television application contemplated in the Cordell patent.
Due to the difficulty of implementing high-speed VWL decoders, there have been several special VWL codes designed for fast decoders. For example, a VWL code with a length-indicating prefix is proposed by J. Cocke et al. in U.S. Pat. No. 3,717,851. Such approaches trade off coding efficiency against hardware speed.
In many computer imaging applications, the speed at which images can be displayed is an important factor in achieving user acceptance. For example, where computer-based X-ray image display systems are employed in a medical environment to replace film images, users demand the ability to select, view and manipulate the images at least as rapidly as they could with ordinary film. Thus, in evaluating the application of a VWL decoder in a medical imaging workstation, it was determined that a decoding rate of at least 25 million pixels per second was desirable to meet the performance requirements of system users.
However, the practical limit to the decoding rate for the serial tree searching technique is about 40-50 million bits per second using present bipolar and CMOS semiconductor technology. At an average of 6 bits per pixel, this amounts to only 7-8 million pixels per second. Even using a lookup table and a commercially available barrel shifter to decode Huffman codes, as described in Arbeiter, a decoding rate of approximately only 15 million pixels per second is achievable.
Thus, prior art decoding techniques which use commercially feasible technology fail to satisfy system performance requirements. Although some fast decoders are available, they either require special codes which provide poor data compression efficiency, or they require exotic components which are too expensive for the intended commercial applications.